//
//  ThreeSumMulti.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/28.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  923. 三数之和的多种可能

import UIKit

/*
 923. 三数之和的多种可能
 给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

 由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。

  

 示例 1：

 输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
 输出：20
 解释：
 按值枚举（A[i]，A[j]，A[k]）：
 (1, 2, 5) 出现 8 次；
 (1, 3, 4) 出现 8 次；
 (2, 2, 4) 出现 2 次；
 (2, 3, 3) 出现 2 次。
 示例 2：

 输入：A = [1,1,2,2,2,2], target = 5
 输出：12
 解释：
 A[i] = 1，A[j] = A[k] = 2 出现 12 次：
 我们从 [1,1] 中选择一个 1，有 2 种情况，
 从 [2,2,2,2] 中选出两个 2，有 6 种情况。
  

 提示：

 3 <= A.length <= 3000
 0 <= A[i] <= 100
 0 <= target <= 300
 */

class ThreeSumMulti: NSObject {
    func threeSumMulti(_ A: [Int], _ target: Int) -> Int {
        
        let divisor = 1_000_000_000 + 7
        var resultNum = 0
        
        let A = A.sorted()
        // 0 1 2 3 4
        
        //三指针
        /*
         先固定一个指针p1在索引0的位置  然后把剩下的数组 一前(p1)一后(p2)进行遍历，
         设 T = target - A[p0]
         当 A[p1] + A[p2] > T， p2前移   p2--
         当 A[p1] + A[p2] < T， p1后移   p1++
         直至后两个指针相遇，中途记录每次满足 A[p1] + A[p2] = target - A[p0]的情况。
         
         固定指针逐次往前加1 重复上面操作，即可得出结果
         */
        
        for i in 0 ..< A.count{
            let T = target - A[i]
            var j = i+1
            var k = A.count - 1
            
            while j < k {
                if A[j] + A[k] < T {
                    j += 1
                }else if A[j] + A[k] > T {
                    k -= 1
                }else{
                    //此时有 A[j] + A[k] == T
                    //要处理重复的情况 比如 (2,2,2) target = 6 这种测试用例
                    
                    //如果有 A[j] == A[k]  设 M 表示A[j]在数据源中出现的次数。(M*(M-1))/2 
                    
                    if A[j] != A[k] {

                        var left = 1
                        var right = 1
                        while j+1 < k && A[j] == A[j+1] {
                            left += 1
                            j += 1
                        }
                        while k-1 > j && A[k] == A[k-1] {
                            right += 1
                            k -= 1
                        }
                        resultNum += left * right
                        resultNum = resultNum%divisor
                        j += 1
                        k -= 1
                    }else if A[j] == A[k] {
                        resultNum += (k-j+1)*(k-j)/2
                        resultNum = resultNum%divisor
                        break
                    }
                }
            }
        }
        
        return resultNum
    }
    
    
    
    //尝试回溯算法
    /*
     47 / 70 个测试用例  [0,0,0] 0  正确结果输出 1  本算法输出3   增加当三个数相等时的特判。
     48 / 70 个测试用例  [0,....,0](3000个0) 0  正确结果输出 495500972  本算法耗时直接爆炸 且count为3的结果仅仅输出一个。因此回溯法不适合本题。
     */
    func threeSumMulti2(_ A: [Int], _ target: Int) -> Int {
        
        //求出每个数字在数组中出现的次数
        var numCountDic:[Int:Int] = [:]
        for num in A{
            if numCountDic[num] == nil {
                numCountDic[num] = 1
            }else{
                numCountDic[num]! += 1
            }
        }
        
        let arr = self.combinationSum2(A, target)
        //print("\(arr)")
        
        var threeNumArr:[[Int]] = []
        for allRes in arr{
            if allRes.count == 3 {
                threeNumArr.append(allRes)
            }
        }
        
        var sum = 0
        for threeRes in threeNumArr{
            let a0 = threeRes[0]
            let a0Count = numCountDic[a0]!
            
            let a1 = threeRes[1]
            let a1Count = numCountDic[a1]!
            
            let a2 = threeRes[2]
            let a2Count = numCountDic[a2]!
            
            
            if threeRes[0] != threeRes[1] && threeRes[1] != threeRes[2]{
                //三个数字各不相等，
                sum += a0Count * a1Count * a2Count
                
            }else if threeRes[0] == threeRes[1] && threeRes[1] != threeRes[2]{
                //前两个数字相等 和后一个数字不相等
                sum += (a0Count * (a0Count-1))/2 * a2Count
                
            }else if threeRes[0] != threeRes[1] && threeRes[1] == threeRes[2]{
                //后两个数字相等 和前一个数字不相等
                sum += (a2Count * (a2Count-1))/2 * a0Count
                
            }else if threeRes[0] == threeRes[1] && threeRes[1] == threeRes[2]{
                //三个数字都相等
                if A.count == 3 {
                    sum += 1
                }else{
                    sum += numCountDic[a0]!
                }
            }
        }
        
        let mod = 1_000_000_000 + 7
        
        return sum%mod
    }
    
    
    var resultArr:Array<[Int]> = []
    
    
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
    
        if candidates.count == 0{
            return resultArr
        }
        
        let sourceArr = candidates.sorted()
        
        let arr = [Int]()
        
        self.dfs(0, arr, sourceArr, target)
        
        return resultArr
        
    }
    
    func dfs(_ startIndex: Int, _ tmpArr: [Int] , _ sourceArr: [Int] ,_ target: Int){
        
        //print("\(target)")
        if target == 0 {
            resultArr.append(tmpArr)
            //print("\(tmpArr)")
        }
        
        var arr = tmpArr
        for index in startIndex ..< sourceArr.count {
            if target - sourceArr[index] < 0 {
                break;
            }
            if index > startIndex && sourceArr[index] == sourceArr[index - 1]{
                continue
            }
            arr.append(sourceArr[index])
            //print("---------------内部循环第\(startIndex)次")
            self.dfs(index + 1, arr, sourceArr, target-sourceArr[index])
            arr.removeLast()
        }
    }
}
